package templates;

import java.util.Arrays;

public class QuickSortTemp {

    public static void main(String[] args) {
        int[] arr = {0,1,1,0,2,2};
        // 定义容器保存结果
        quickSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr,int left,int right) {
        if (left >= right){
            return;
        }

        int leftIndex = left;
        int rightIndex = right;
        int num = arr[left];
        while (leftIndex < rightIndex){
            while (leftIndex < rightIndex && arr[rightIndex] >=  num){
                rightIndex --;
            }
            while (leftIndex < rightIndex && arr[leftIndex] <= num){
                leftIndex ++;
            }
            if (leftIndex < rightIndex){
                int temp = arr[leftIndex];
                arr[leftIndex] = arr[rightIndex];
                arr[rightIndex] = temp;
            }
        }

        arr[left] = arr[leftIndex];
        arr[leftIndex] = num;

        quickSort(arr,left,leftIndex - 1);
        quickSort(arr,leftIndex + 1,right);
    }
}
